package com.leetcode.algorithm.y22.m07.w4;

import com.leetcode.algorithm.common.TreeNode;

/**
 * 108. 将有序数组转换为二叉搜索树
 * 
 * https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/
 * 
 * @author jie.deng
 *
 */
class Question0108Solution01 {

	public TreeNode sortedArrayToBST(int[] nums) {
		int len = nums.length;
		return sortedArrayToBST(nums, 0, len - 1);
	}

	private TreeNode sortedArrayToBST(int[] nums, int left, int right) {
		if (left > right) {
			return null;
		}
		if (left == right) {
			return new TreeNode(nums[left]);
		}
		int mid = left + ((right - left) >> 1);
		TreeNode root = new TreeNode(nums[mid]);
		root.left = sortedArrayToBST(nums, left, mid - 1);
		root.right = sortedArrayToBST(nums, mid + 1, right);
		return root;
	}

}